Section: Scientific Foundations

Reliable geometric computations on curves and surfaces

Keywords: Effective geometry, robustness, geometric predicates, intersection detection.

Simple algebraic surfaces cover a variety of forms sufficient for representing the majority of objects encountered in the fields of design, architecture and industrial manufacturing. For instance, it has been estimated that 95% of all mechanical pieces can be well modeled by quadric patches (degree 2 surfaces, including planes, spheres, cylinders and cones) and torii  [38] . It is important, then, to be able to process these surfaces in a robust and efficient manner.

In comparison with polygonal representations, modeling and manipulating scenes made of curved objects pose a large variety of new issues and require entirely different tools. It is for instance no longer realistic to assume that simple operations like intersecting two primitives take constant time. The usual notion of complexity has to be revised and needs to incorporate the arithmetic complexity of operations.

Geometric computing with curved objects is plagued with robustness issues. The numerical instability of geometric algorithms is intimately linked to the double nature of geometric objects. Indeed, a geometric object is two things: a combinatorial structure which encodes the incidence properties between the elements constituting the object, and numerical quantities (coordinates, equations) describing the embedding of the object in space. Manipulating geometric data, without breaking the consistency constraints that govern the relation between combinatorial and numerical quantities, is usually hard and has led to the unfolding of the exact geometric computing paradigm.

The dependence of combinatorial decisions on numerical computations is encapsulated in the notion of geometric predicates. When working with algebraic objects, evaluating a geometric predicate often means determining the sign of a polynomial expression in the coefficients of the input. This sign encodes the answer to simple geometric queries like “are three given points aligned?” or “is a given line tangent to a given surface?”. The paradigm of exact geometric computing requires the predicates to be evaluated exactly, ensuring that the branching of the algorithm are correct, that the software will not crash, loop indefinitely or output a wrong answer, and thus that the topological structure of the output is correct.

In the context of exact geometric computing, we work on key problems involving curved objects, mainly two-dimensional curves, and low-degree three-dimensional surfaces such as quadrics. For instance, we study intersections of quadrics both from an algorithmic and an algebraic-geometric point of view. On the algorithmic side, we work on finding simple and usable parameterizations of the intersection of two arbitrary quadrics. On the algebraic side, we deal with finding simple (and ideally optimal) geometric predicates for classifying the intersection pattern and the positional relationship of two quadrics.

We also work on computing arrangements of curved objects, i.e. the partitioning of space induced by the objects, such as arrangements of curves on a surface, or arrangements of quadrics in 3D space. Note that intersections of 2 and 3 quadrics are building blocks for the constructions of quadric arrangements. We work on constructing simpler sub-arrangements, like the BRep (Boundary Representation) of a solid model (CSG). Exact CSG-to-BRep conversion is a key and long-standing problem in CAGD, where many conventional modelers work with volumes, and rendering software based on the global illumination approach need surface patches.

Finally, we deal with geometric problems where low-degree surfaces appear indirectly, not in the input but as intermediate structures. A major problem in this category is the computation of the Voronoi diagram, or medial axis, of polyhedra in 3D. In particular, we work on the simpler instance where only lines and line segments in 3D are considered, the bisectors of pairs of lines being quadric surfaces.